/*
题目: 二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。
https://leetcode.cn/problems/find-mode-in-binary-search-tree
 */
public class FindMode {
    List<Integer> list = new ArrayList<> ();
    int mode = Integer.MAX_VALUE; //众数
    int maxCnt = 0;
    int cnt = 0;

    public int[] findModeRecursion (TreeNode root) {
        dfs(root);

        int[] res = new int[list.size()];
        int len = list.size();
        for (int i = 0; i < len; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        judgeMode(root.val);
        dfs(root.right);
    }

    private void judgeMode(int val) {
        if (val == mode) {
            cnt++;
        } else {
            cnt = 1;
            mode = val;
        }

        if (cnt > maxCnt) {
            maxCnt = cnt;
            list.clear();
            list.add(mode);
        } else if (cnt == maxCnt) {
            list.add(mode);
        }
    }

    /**
     * 非递归做法
     */

    /*
    List<Integer> list = new ArrayList<> ();
    int mode = Integer.MAX_VALUE; //众数
    int maxCnt = 0;
    int cnt = 0;

    public int[] findMode(TreeNode root) {
        Stack<TreeNode> stack = new Stack<> ();

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            judgeMode(root.val);
            root = root.right;
        }


        int[] res = new int[list.size()];
        int len = list.size();
        for (int i = 0; i < len; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void judgeMode(int val) { //判断众数
        if (val == mode) {
            cnt++;
        } else {
            cnt = 1;
            mode = val;
        }

        if (cnt > maxCnt) {
            maxCnt = cnt;
            list.clear();
            list.add(mode);
        } else if (cnt == maxCnt) {
            list.add(mode);
        }
    }
     */

    /**
     * Morris遍历
     */

    /*
    List<Integer> list = new ArrayList<> ();
    int mode = Integer.MAX_VALUE; //众数
    int maxCnt = 0;
    int cnt = 0;

    public int[] findMode(TreeNode root) {
        //Morris遍历
        while (root != null) {
            TreeNode success = root.left;
            if (success != null) {  //如果左子树不为空
                while (success.right != null && success.right != root) {
                    success = success.right;
                }
                if (success.right == null) {  //如果还没线索化
                    success.right = root;
                    root = root.left;
                } else {  //如果已经线索化
                    success.right = null; //断开链接
                    judgeMode(root.val);
                    root = root.right;
                }
            } else {  //如果左子树为空
                judgeMode(root.val);
                root = root.right;
            }
        }

        int[] res = new int[list.size()];
        int len = list.size();
        for (int i = 0; i < len; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void judgeMode(int val) { //判断众数
        if (val == mode) {
            cnt++;
        } else {
            cnt = 1;
            mode = val;
        }

        if (cnt > maxCnt) {
            maxCnt = cnt;
            list.clear();
            list.add(mode);
        } else if (cnt == maxCnt) {
            list.add(mode);
        }
    }
     */
}
